package com.da.javatest.niuke.baodian;

import java.util.Arrays;

/**
 * @author chenlida
 * @date 2020/10/18 11:02
 * https://www.nowcoder.com/practice/93579c39385447f3a0ea5759902e3e0c?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C79Middle {
    public static int[] getMiddle(int[] A, int n) {
        int[] data = new int[n];
        int sum = 0;
        for (int i = 0, count = 1; i < A.length; i++, count++) {
            sum += A[i];
            // 求平均数
            int avg = sum / count;
            data[i] = A[i];
            int mid = Math.abs(A[i] - avg);
            // 拿到差值最小的作为中间数
            for (int j = 0; j <= i; j++) {
                int abs = Math.abs(A[j] - avg);
                if (abs < mid) {
                    mid = abs;
                    data[i] = A[j];
                }
            }
        }
        return data;
    }

    public static int[] getMiddle2(int[] A, int n) {
        int[] res = new int[A.length];
        res[0] = A[0];
        for (int i = 1; i < A.length; i++) {
            int k = i - 1;
            int tem = A[i];
            while (k >= 0 && A[k] > tem) {
                A[k + 1] = A[k];
                k--;
            }
            A[++k] = tem;
            res[i] = A[i / 2];
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(getMiddle2(new int[] {236312, 116289, 257841, 40359, 21993, 121674, 68768}, 7)));
    }
}
